package collect;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.SortedSet;

/**
 * This class is a light-weight adaptor wrapping an immutable range of integers in the
 * {@link List} and {@link SortedSet} interfaces.
 * @author Carl Pearson
 */
public abstract class Range implements SortedSet<Integer>, List<Integer> {

	public static final Range range(int first, int last) {
		if (first < last) return new RegularRange(first,last);
		if (first == last) return new SingletonRange(first);
		return null;
	}
	
	public static final Range range(int last) {
		return range(0,last);
	}
	
	public Range() {}

	@Override public abstract Integer first();
	@Override public abstract Integer last();
	
	private static class SingletonRange extends Range {
		private final int item;
		SingletonRange(final int item) {
			this.item = item;
		}
		@Override public Integer first() { return item; }
		@Override public Integer last() { return item; }
		@Override public int size() { return 1; }
		
		@Override public Range headSet(Integer toElement) {
			if (toElement == null) throw new NullPointerException();
			if (toElement > item) return this;
			return Empty.get();
		}
		
		@Override public Range tailSet(Integer fromElement) {
			if (fromElement == null) throw new NullPointerException();
			if (fromElement <= item) return this;
			return Empty.get();
		}
		
	}
	
	private static class RegularRange extends Range {

		private final int first;
		private final int last;
		private final int size;
		
		RegularRange(final int first, final int last) {
			this.first = first;
			this.last = last;
			this.size = last - first + 1;
		}

		@Override public Integer first() { return first; }
		@Override public Integer last() { return last; }
		@Override public int size() { return size; }
		
	}
	
	@Override public Range headSet(Integer toElement) {
		if (toElement == null) throw new NullPointerException();
		if (toElement - 1 > last()) return this;
		if (toElement - 1 < first()) return Empty.get();
		return new Head(toElement-1, this);
	}
	
	private class Head extends Range {
		private final Integer last;
		private final Range delegate;
		public Head(Integer last, Range delegate) {
			this.last = last;
			this.delegate = delegate;
		}
		@Override public Integer first() { return delegate.first(); }
		@Override public Integer last() { return last; }
	}
	
	@Override public Range tailSet(Integer fromElement) {
		if (fromElement==null) throw new NullPointerException();
		if (fromElement > last()) return Empty.get();
		if (fromElement < first()) return this;
		return new Tail(fromElement, this);
	}
	
	private class Tail extends Range {
		private final Integer first;
		private final Range delegate;
		public Tail(Integer first, Range delegate) {
			this.first = first;
			this.delegate = delegate;
		}
		@Override public Integer first() { return first; }
		@Override public Integer last() { return delegate.last(); }
	}
	
	@Override public Range subSet(Integer from, Integer to) {
		if (from == null || to == null || from > to) throw new IllegalArgumentException();
		return new RegularRange(
				from < first() ? first() : from,
				to - 1 > last() ? last() : to - 1);
	}
	
	@Override
	public boolean contains(Object o) {
		return 	!(o instanceof Integer) ? false : contains((Integer)o);
	}
	
	private boolean contains(Integer o) {
		return first() <= o && o <= last();
	}

	@Override public boolean containsAll(Collection<?> c) {
		for (Object o : c) if (!contains(o)) return false;
		return true;
	}

	@Override public Integer get(int index) {
		if (index < 0 || index >= size()) throw new IndexOutOfBoundsException();
		return first() + index;
	}
	
	@Override public boolean isEmpty() { return false; }

	@Override public Iterator<Integer> iterator() { return new Counter(); }

	@Override public int size() { return last() - first() + 1; }

	@Override public Object[] toArray() {
		Integer[] array = new Integer[size()];
		for (int i=0; i<array.length; i++) array[i]=i+first();
		return array;
	}

	@SuppressWarnings("unchecked")
	@Override public <T> T[] toArray(T[] a) {
		if (!(a instanceof Integer[])) throw new ClassCastException();
		if (a.length < size()) a = Arrays.copyOf(a, size());
		
		for (Integer i=0, value = i+first(); i<size(); i++, value=i+first()) a[i]=(T)value;

		if (a.length > size()) for (int i=size() ; i<a.length ; i++) a[i]=null;
		return a;
	}
	
	public static final Comparator<Integer> comparator = new Comparator<Integer>() {
		@Override public int compare(Integer arg0, Integer arg1) {
			return arg0 == null ? arg1 == null ? 0 : 1 : arg0.compareTo(arg1);
		}
	};
	
	@Override public Comparator<Integer> comparator() { return comparator; }

	@Override
	public int indexOf(Object o) {
		return contains(o) ? indexOf((Integer)o) : -1;
	}

	@Override
	public int lastIndexOf(Object o) {
		return contains(o) ? indexOf((Integer)o) : -1;
	}
	
	private int indexOf(Integer o) {
		return o - first();
	}

	@Override
	public ListIterator<Integer> listIterator() {
		return new Counter();
	}

	@Override
	public ListIterator<Integer> listIterator(int index) {
		return new Counter(index);
	}

	@Override
	public Range subList(int fromIndex, int toIndex) {
		if (fromIndex < 0 || toIndex > size()) throw new IndexOutOfBoundsException();
		if (fromIndex == toIndex) return Empty.get();
		return new RegularRange(get(fromIndex),get(toIndex-1));
	}
	
	public class Counter implements ListIterator<Integer> {

		private Integer prev;
		private Integer next;
		
		public Counter() { next = first(); }
		public Counter(int index) {
			if (index < 0 || index >= size()) throw new IndexOutOfBoundsException();
			next = get(index);
			if (index > 0) prev = get(index-1);
		}
		
		@Override public void add(Integer arg0) { throw immutable(); }
		@Override public void remove() { throw immutable(); }
		@Override public void set(Integer arg0) { throw immutable(); }

		@Override
		public boolean hasNext() {
			return next != null;
		}

		@Override
		public boolean hasPrevious() {
			return prev != null;
		}

		@Override
		public Integer next() {
			if (hasNext()) {
				prev = next;
				next = contains(next+1) ? next + 1 : null ;
				return prev;
			} else throw new NoSuchElementException();
		}

		@Override
		public int nextIndex() { return next == null ? -1 : indexOf(next); }

		@Override
		public Integer previous() {
			if (hasPrevious()) {
				next = prev;
				prev = contains(prev-1) ? prev - 1 : null ;
				return next;
			} else throw new NoSuchElementException();
		}

		@Override
		public int previousIndex() {
			return prev == null ? -1 : indexOf(prev);
		}
		
	}
	
	/**
	 * @return the exception thrown when attempting to mutate a Range.
	 */
	public static final UnsupportedOperationException immutable() {
		return new UnsupportedOperationException();
	}
	
	/**
	 * Guaranteed to throw an {@link UnsupportedOperationException}.
	 */
	@Override public final boolean add(Integer e) {
		throw immutable(); }
	
	/**
	 * Guaranteed to throw an {@link UnsupportedOperationException}.
	 */
	@Override public final boolean addAll(Collection<? extends Integer> c) {
		throw immutable(); }
	
	/**
	 * Guaranteed to throw an {@link UnsupportedOperationException}.
	 */
	@Override public final void clear() {
		throw immutable(); }
	
	/**
	 * Guaranteed to throw an {@link UnsupportedOperationException}.
	 */
	@Override public boolean remove(Object o) {
		throw immutable(); }
	
	/**
	 * Guaranteed to throw an {@link UnsupportedOperationException}.
	 */
	@Override public boolean removeAll(Collection<?> c)	{
		throw immutable(); }
	
	/**
	 * Guaranteed to throw an {@link UnsupportedOperationException}.
	 */
	@Override public boolean retainAll(Collection<?> c) {
		throw immutable(); }
	
	/**
	 * Guaranteed to throw an {@link UnsupportedOperationException}.
	 */
	@Override public Integer remove(int index) {
		throw immutable(); }
	
	/**
	 * Guaranteed to throw an {@link UnsupportedOperationException}.
	 */
	@Override public Integer set(int index, Integer element) {
		throw immutable(); }
	
	/**
	 * Guaranteed to throw an {@link UnsupportedOperationException}.
	 */
	@Override public void add(int index, Integer element) {
		throw immutable(); }

	/**
	 * Guaranteed to throw an {@link UnsupportedOperationException}.
	 */
	@Override public boolean addAll(int index, Collection<? extends Integer> c) {
		throw immutable(); }
	
	private static class Empty extends Range {

		private static final Empty instance = new Empty();
		
		private Empty() {}
		
		@Override
		public boolean contains(Object o) {
			if (o == null) throw new NullPointerException();
			if (!(o instanceof Integer)) throw new ClassCastException();
			return false;
		}

		public static Range get() {
			return instance;
		}

		@Override
		public boolean containsAll(Collection<?> c) {
			return c.isEmpty();
		}

		@Override
		public Integer first() { throw new NoSuchElementException(); }

		@Override
		public Integer get(int index) {
			throw new IndexOutOfBoundsException();
		}

		@Override public Range headSet(Integer toElement) {
			if (toElement == null) throw new NullPointerException();
			return this;
		}

		@Override
		public int indexOf(Object o) {
			if (o == null) throw new NullPointerException();
			if (!(o instanceof Integer)) throw new ClassCastException();
			return -1;
		}

		@Override public boolean isEmpty() { return true; }

		@Override
		public Iterator<Integer> iterator() {
			return Collections.<Integer>emptyList().iterator();
		}

		@Override
		public Integer last() { throw new NoSuchElementException(); }

		@Override
		public int lastIndexOf(Object o) { 
			if (o == null) throw new NullPointerException();
			if (!(o instanceof Integer)) throw new ClassCastException();
			return -1;
		}

		@Override
		public ListIterator<Integer> listIterator() {
			return Collections.<Integer>emptyList().listIterator();
		}

		@Override
		public ListIterator<Integer> listIterator(int index) {
			return Collections.<Integer>emptyList().listIterator(index);
		}
		
		@Override public int size() { return 0; }

		@Override
		public Range subList(int fromIndex, int toIndex) {
			if (toIndex != 0 && fromIndex != toIndex) throw new IndexOutOfBoundsException();
			return this;
		}

		@Override
		public Range subSet(Integer from, Integer to) {
			if (from == null || to == null) throw new NullPointerException();
			return this;
		}

		@Override public Range tailSet(Integer fromElement) {
			if (fromElement == null) throw new NullPointerException();
			return this;
		}

		@Override public Object[] toArray() { return new Integer[0]; }

		@Override public <T> T[] toArray(T[] a) {
			Arrays.fill(a, null);
			return a;
		}

		@Override
		public boolean equals(Object obj) {
			return obj instanceof Empty;
		}

		@Override
		public int hashCode() { return 1; }

		@Override public String toString() { return "Empty Range"; }
		
	}
	
	private Integer hash;
	@Override public int hashCode() {
		if (hash == null) {
			int result = 1;
			for (Integer i : this) result = result*31 + i.hashCode();
			hash = result;
		}
		return hash;
	}

	@Override public String toString() {
		StringBuilder result = new StringBuilder("[ ").append(get(0));
		for (int i = 1; i<size(); i++) result.append(", "+get(i));
		return result.append(" ]").toString();
	}
	
	@Override public boolean equals(Object o) {
		return !(o instanceof List<?>) ? false : equals((List<?>)o);
	}
	
	private boolean equals(List<?> o) {
		if (o.size() != size()) return false;
		if (o instanceof Range) return equals((Range)o);
		Iterator<?> other = o.iterator();
		Iterator<Integer> me = iterator();
		while (me.hasNext() && other.hasNext()) if (!me.next().equals(other.next())) return false;
		return true;
	}
	
	private boolean equals(Range o) {
		return first().equals(o.first()) && last().equals(o.last());
	}
}
